package com.sheng.leetcode.year2022.month08.day22;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author liusheng
 * @date 2022/08/22
 *
 * 655. 输出二叉树
 *
 * 给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
 * 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
 * 矩阵的列数 n 应该等于 2^(height+1) - 1 。
 * 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
 * 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2^(height-r-1)] ，右子节点放置在 res[r+1][c+2^(height-r-1)] 。
 * 继续这一过程，直到树中的所有节点都妥善放置。
 * 任意空单元格都应该包含空字符串 "" 。
 * 返回构造得到的矩阵 res 。
 *
 * 示例 1：
 * 输入：root = [1,2]
 * 输出：
 * [[" ","1"," "],
 *  ["2"," "," "]]
 *
 * 示例 2：
 * 输入：root = [1,2,3,null,4]
 * 输出：
 * [[" "," "," ","1"," "," "," "],
 *  [" ","2"," "," "," ","3"," "],
 *  [" "," ","4"," "," "," "," "]]
 *
 * 提示：
 *
 * 树中节点数在范围 [1, 210] 内
 * -99 <= Node.val <= 99
 * 树的深度在范围 [1, 10] 内
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/print-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0655 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        left.right = new TreeNode(4);
        root.left = left;
        root.right = new TreeNode(3);
        System.out.println(new Solution().printTree(root).toString());
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * height：二叉树高度从0开始计算
     * m：二维数组的长度
     * n：二维数组的长度
     */
    int height = 0;
    int m;
    int n;
    public List<List<String>> printTree(TreeNode root) {
        // 获取二叉树的高度
        List<TreeNode> treeNodes = new ArrayList<>();
        treeNodes.add(root);
        // 获取二叉树的高度
        bfs(treeNodes);
        // 求得二维数组的长度
        m = height + 1;
        n = (1 << (height + 1)) - 1;
        String[][] strings = new String[m][n];
        // 给二维数组赋初始值""
        for (int i = 0; i < strings.length; i++) {
            for (int j = 0; j < strings[0].length; j++) {
                strings[i][j] = "";
            }
        }
        // 遍历放入所有的结点值
        putValue(strings, root, 0, (n - 1) / 2);
        // 二维数组转集合
        return Arrays.stream(strings).map(i -> Arrays.stream(i).collect(Collectors.toList())).collect(Collectors.toList());
    }

    /**
     * 将对应二叉树的结点值放入二维数组中
     *
     * @param strings 二维数组
     * @param root 二叉树结点
     * @param index1 结点坐标
     * @param index2 结点坐标
     */
    public void putValue(String[][] strings, TreeNode root, int index1, int index2) {
        strings[index1][index2] = String.valueOf(root.val);
        if (root.left != null) {
            putValue(strings, root.left, index1 + 1, index2 - (1 << (height - index1 - 1)));
        }
        if (root.right != null) {
            putValue(strings, root.right, index1 + 1, index2 + (1 << (height - index1 - 1)));
        }
    }

    /**
     * 层序遍历二叉树，获取高度
     *
     * @param list 二叉树结点集合
     */
    public void bfs(List<TreeNode> list) {
        List<TreeNode> treeNodes = new ArrayList<>();
        for (TreeNode treeNode : list) {
            if (treeNode.left != null) {
                treeNodes.add(treeNode.left);
            }
            if (treeNode.right != null) {
                treeNodes.add(treeNode.right);
            }
        }
        if (treeNodes.size() > 0) {
            height++;
            bfs(treeNodes);
        }
    }
}
